package lc_2961_双模幂运算;

import java.util.ArrayList;
import java.util.List;

public class Solution {

	private long pow1(long base, long exp, int mod) {
		if (exp == 0) {
			return 1;
		}
		long b = pow(base, exp >> 1, mod) % mod;
		long bb = b * b % mod;
		return (exp & 1) == 0 ? bb : bb * base % mod;
	}

	private long pow(long base, long exp, int mod) {
		long ans = 1;
		while (exp > 0) {
			if ((exp & 1) == 1) {
				ans = ans * base % mod;
			}
			base = base * base % mod;
			exp >>= 1;
		}
		return ans;
	}

	public List<Integer> getGoodIndices(int[][] variables, int target) {
		List<Integer> ans = new ArrayList<>();

		for (int i = 0; i < variables.length; i++) {
			int[] var = variables[i];
			int a = var[0], b = var[1], c = var[2], m = var[3];
			if (pow(pow(a, b, 10), c, m) == target) {
				ans.add(i);
			}
		}

		return ans;
	}

}